package com.mlh.stack;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author 缪林辉
 * @date 2024/3/22 23:18
 * @DESCRIPTION
 */

// 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
// 在 S 上反复执行重复项删除操作，直到无法继续删除。
// 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
// 示例：
// 输入："abbaca"
// 输出："ca"
// 解释：
// 例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。
// 之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

public class RemoveDuplicates {
    // 思路：第一个字符入栈，第二个字符入栈时对比栈顶元素，如果和栈顶元素相同，则弹出栈顶元素，且跳过第二个字符
    // 如果不相同，第二个字符入栈
    // 重复以上过程即可
    public String method2(String s) {
        Stack<Character> stack = new Stack();
        stack.push(s.charAt(0));
        int num = 1;
        for (int i = 1; i < s.length(); i++) {
            if (!stack.empty() && stack.peek() == s.charAt(i)) {
                stack.pop();
                num--;
            } else {
                stack.push(s.charAt(i));
                num++;
            }
        }
        char[] res = new char[num];
        while (!stack.empty()) {
            res[num - 1] = stack.pop();
            num--;
        }
        return new String(res);
    }

    // 这道题是可以利用栈来实现，method1向右数组加双指针来模拟栈解决该问题的方式
    // 后面发现没办法利用双指针去实现这一过程，在某些情况下会失效
    public String method1(String s) {
        char[] chars = s.toCharArray();
        int first = 1, after = 0;
        while (first < chars.length) {
            if (chars[first] == chars[after]) {
                chars[first] = 'A';
                chars[after] = 'A';
                after--;
                first++;
                if (after < 0) {
                    after = first;
                    first++;
                }
                continue;
            }
            after = first;
            first++;
        }
        char[] charNew = new char[s.length()];
        int index = 0;
        for (int i = 0; i < s.length(); i++) {
            if (chars[i] != 'A') {
                charNew[index++] = chars[i];
            }
        }
        return new String(charNew, 0, index);
    }

    public String method3(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (sb.length() != 0 && sb.charAt(sb.length() - 1) == c) {
                sb.deleteCharAt(sb.length() - 1);
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}
